const ON_LEFT_SIDE = 1
const ON_RIGHT_SIDE = 2
const ON_LINE_IN = 3
const ON_LINE_OUT = 4
const BETWEEN_IN = 1
const BETWEEN_ON = 2
const BETWEEN_NOT = 3
const POLYGON_INSIDE = 1
const POLYGON_ON_EDGE = 2
const POLYGON_OUTSIDE = 3

let precision = -1
let minimum = 1
const EPS = 0.000001 // Number.EPSILON
const bool_union = 'union' // 求两个图形的合并
const bool_a_sub_b = 'subtraction' // 求图形a 减去 图形b后得到的图形列表, 图形a为被挖孔对象
const bool_intersection = 'intersection' // 求图形a 和 图形b 相交后得到的图形列表

// 集合A - 集合B，arrA 会被修改，arrB不改变
function arrAsubB(arrA, arrB) {
  arrB.forEach(it => {
    const ind = arrA.indexOf(it)
    if (ind >= 0) {
      arrA.splice(ind, 1)
    }
  })
  return arrA
}

// 集合A 与 集合B 的并集，arrA 会被修改，arrB不改变
function arrAonB(arrA, arrB) {
  const shared = []
  arrB.forEach(it => {
    const ind = arrA.indexOf(it)
    if (ind >= 0) {
      shared.push(it)
    }
  })
  arrA.splice(0, arrA.length)
  arrA.push(...shared)
  return arrA
}

function equals(pt0, pt1, notPrecise = true) {
  if (pt0 === pt1) {
    return true
  }
  if (notPrecise) {
    return Math.abs(pt0.x - pt1.x) < minimum && Math.abs(pt0.y - pt1.y) < minimum
  }
  return pt0.x === pt1.x && pt0.y === pt1.y
}

function edges2Points(edges) {
  const points = []
  if (edges.length > 0) {
    edges.forEach(edge => {
      if (points.indexOf(edge.from) < 0) {
        points.push(edge.from)
      }
      if (points.indexOf(edge.to) < 0) {
        points.push(edge.to)
      }
    })
  }
  return points
}

class Edge {
  splitBy = []
  _checked = false
  /**
   * @type {Edge}
   */
  reversedTo
  /**
   * @type {Edge}
   */
  reversedFrom

  /**
   * @param {{x: number, y: number}} from 起点
   * @param {{x: number, y: number}} to 终点
   * @param {number} belong 属于哪个多边形
   * @param {number} holeId 属于多边形的哪个轮廓
   */
  constructor(from, to, belong = -1, holeId = -1) {
    this.from = from
    this.to = to
    this.belong = belong
    this.holeId = holeId
  }

  addSplitBy(point) {
    if (!equals(this.from, point) && !equals(this.to, point) && this.splitBy.indexOf(point) < 0) {
      this.splitBy.push(point)
      return point
    }
    return null
  }

  setChecked() {
    this._checked = true
  }

  getChecked() {
    return this._checked
  }

  reverseEdge() {
    if (this.reversedTo) {
      return this.reversedTo
    }
    const edge = new Edge(this.to, this.from, this.belong, this.holeId)
    edge.reversedFrom = this
    this.reversedTo = edge
    return edge
  }

  clone() {
    return new Edge(this.to, this.from, this.belong, this.holeId)
  }

  setFrom(from) {
    this.from = from
    return this
  }

  setTo(to) {
    this.to = to
    return this
  }

  sliceBy(crossPoint) {
    return [this.clone().setTo(crossPoint), this.clone().setFrom(crossPoint)]
  }

  sourceId() {
    const maxX = Math.max(this.from.x, this.to.x)
    const minX = Math.min(this.from.x, this.to.x)
    const maxY = Math.max(this.from.y, this.to.y)
    const minY = Math.min(this.from.y, this.to.y)
    return maxX + ',' + minX + ';' + maxY + ',' + minY
  }

  sameSource(edge) {
    if (equals(this.from, edge.from) && equals(this.to, edge.to)) {
      return {similarType: 4} // 端点相同，方向也相同
    } else if (equals(this.from, edge.to) && equals(this.to, edge.from)) {
      return {similarType: 3} // 端点相同，方向正好相反
    }
    return null
  }

  getMidPoint() {
    return {x: (this.from.x + this.to.x) / 2, y: (this.from.y + this.to.y) / 2}
  }

  get length() {
    return getDistance(this.from, this.to)
  }

  lerpToEnd(alpha) {
    const x = this.from.x + (this.to.x - this.from.x) * alpha
    const y = this.from.y + (this.to.y - this.from.y) * alpha
    return {x: x, y: y}
  }

  vertical() {
    return Math.abs(this.from.x - this.to.x) <= minimum
  }

  subEdge(other) {
    if (this.sameSource(other)) {
      return []
    }
    const arr = specialSegmentCross(this.from, this.to, other.from, other.to)
    if (arr.length === 0) {
      return [this]
    }

    const belong = this.belong
    const holeId = this.holeId
    if (arr.indexOf(this.from) >= 0 && arr.indexOf(this.to) >= 0) {
      return []
    } else if (arr.indexOf(this.from) < 0 && arr.indexOf(this.to) < 0) {
      const d1 = getDistanceSquare(this.from, other.from); const d2 = getDistanceSquare(this.from, other.to)
      if (d1 < d2) {
        return [new Edge(this.from, other.from, belong, holeId), new Edge(other.to, this.to, belong, holeId)]
      } else {
        return [new Edge(this.from, other.to, belong, holeId), new Edge(other.from, this.to, belong, holeId)]
      }
    } else {
      const pc = arr.indexOf(other.from) >= 0 ? other.from : other.to
      if (arr.indexOf(this.from) >= 0) {
        return [new Edge(pc, this.to, belong, holeId)]
      } else {
        return [new Edge(this.from, pc, belong, holeId)]
      }
    }
  }
}

class Box2 {
  constructor(min, max) {
    this.min = min
    this.max = max
  }

  // p正好在二维包围盒的边上时，return false;
  contain(p) {
    const yMid = p.y < this.max.y && p.y > this.min.y
    const xMid = p.x < this.max.x && p.x > this.min.x
    return ((xMid && yMid) ||
      (p.x === this.max.x && this.max.x === this.min.x && yMid) ||
      (p.y === this.max.y && this.max.y === this.min.y && xMid))
  }

  scale(scalar) {
    const min = this.min
    const max = this.max
    const center = {x: (min.x + max.x) / 2, y: (min.y + max.y) / 2}
    let dx = center.x - min.x
    let dy = center.y - min.y
    dx *= scalar
    dy *= scalar
    min.x = center.x - dx
    min.y = center.y - dy
    max.x = center.x + dx
    max.y = center.y + dy
  }
}

function findBox2(vertices) {
  const max = {}
  const min = {}
  const arrX = []
  const arrY = []
  vertices.forEach(it => {
    arrX.push(it.x)
    arrY.push(it.y)
  })
  max.x = Math.max(...arrX)
  max.y = Math.max(...arrY)
  min.x = Math.min(...arrX)
  min.y = Math.min(...arrY)
  return new Box2(min, max)
}

function findOutestPoint(vertices, box2) {
  const distances = []
  const boxCenter = {x: (box2.max.x + box2.min.x) / 2, y: (box2.max.y + box2.min.y) / 2}
  for (const vertex of vertices) {
    if (box2.contain(vertex)) {
      distances.push(-1)
    } else {
      distances.push(getDistanceSquare(boxCenter, vertex))
    }
  }
  const max = Math.max(...distances)
  if (max < 0) {
    return null
  }
  return vertices[distances.indexOf(max)]
}

function findStartEdgeOfHole(restEdges0, restEdges1) {
  const restEdges = restEdges0.concat(restEdges1)
  const filtered = restEdges.filter(arr => arr.length > 0)
  if (filtered.length === 0) {
    return null
  }
  return filtered[0][0]
}

function findNextEdgeForHole(curEdge, restEdges0, restEdges1) {
  const flatten = []; const candidates = []
  restEdges0.concat(restEdges1).forEach(arr => flatten.push(...arr))
  flatten.forEach(edge => {
    if (edge.from === curEdge.to) { candidates.push(edge) }
  })
  if (candidates.length === 0) {
    console.error('error! findNextEdgeForHole failed to find next')
    return null
  }
  for (const edge of candidates) {
    if (edge.belong !== curEdge.belong) {
      return edge
    }
  }
  return candidates[0]
}

/**
 * 返回集合 splited0 和 splited1 中一条最靠近边缘的Edge
 * @param {Edge[]} splited0
 * @param {Edge[]} splited1
 * @return {Edge|null}
 */
function findStartEdge(splited0, splited1) {
  const vertices0 = edges2Points(splited0); const vertices1 = edges2Points(splited1)
  const box0 = findBox2(vertices0); const box1 = findBox2(vertices1)
  let edges = splited1
  let p = findOutestPoint(vertices1, box0)
  if (p == null) {
    edges = splited0
    p = findOutestPoint(vertices0, box1)
  }
  for (const edge of edges) {
    if (edge.from === p) {
      return edge
    }
  }
  for (const edge of edges) {
    if (edge.to === p) {
      return edge
    }
  }
  console.log('findStartEdge shall not go here')
  return null
}

function findNextEdge(curEdge, edges0, edges1) {
  let first, second
  // if (edges0[0].belong < 0) {
  //   first = edges0, second = edges1;
  // } else if (edges1[0].belong < 0) {
  //   first = edges1, second = edges0;
  // } else
  if (edges0.length > 0 && curEdge.belong === edges0[0].belong) {
    first = edges1
    second = edges0
  } else {
    first = edges0
    second = edges1
  }
  for (let i = 0; i < first.length; i++) {
    const edge = first[i]
    if (edge.from === curEdge.to && curEdge.reverseEdge() !== edge) {
      return edge
    }
  }
  for (let i = 0; i < second.length; i++) {
    const edge = second[i]
    if (edge.from === curEdge.to) {
      return edge
    }
  }
  console.error('findNextEdge shall never go here')
  return null
}

/**
 * 根据 剩余边列表restEdges0， 剩余边列表restEdges1，返回由二维点组成的二维数组output
 * @param {Edge[][]} restEdges0
 * @param {Edge[][]} restEdges1
 * @param {{x: number, y: number}[][]} output
 */
function findHoles(restEdges0, restEdges1, output) {
  const firstEdge = findStartEdgeOfHole(restEdges0, restEdges1)
  if (firstEdge == null) {
    return
  }
  let holePoints = []
  let curEdge = firstEdge
  let holeStart = -1
  holePoints.push(curEdge.from)
  while (true) {
    curEdge = findNextEdgeForHole(curEdge, restEdges1, restEdges0)
    if (curEdge != null) {
      holePoints.push(curEdge.from)
      // check if hole already found
      if (holePoints.length > 2) {
        holeStart = holePoints.indexOf(curEdge.to)
        if (holeStart >= 0) {
          holePoints = holePoints.slice(holeStart, holePoints.length)
          break
        }
      }
    } else {
      break
    }
  }
  if (curEdge == null) {
    return
  }
  const restEdges00 = getRestEdges(restEdges0, holePoints)
  const restEdges01 = getRestEdges(restEdges1, holePoints)
  output.push(holePoints)
  findHoles(restEdges00, restEdges01, output)
}

/**
 *
 * @param {Edge[][]} edges2 待裁减的边
 * @param {{x: number, y: nubmer}[]} excludePoints
 * @param {{x: number, y: nubmer}[]} specialPoints
 * @return {Edge[][]}
 */
function getRestEdges(edges2, excludePoints, specialPoints) {
  const restEdges2 = []
  edges2.forEach(edges => {
    const restEdges = []
    edges.forEach(edge => {
      if (excludePoints.indexOf(edge.from) < 0 && excludePoints.indexOf(edge.to) < 0) {
        // 如果边的两端都不在 excludePoints 数组中，则需要保留
        restEdges.push(edge)
      }
      if (specialPoints && specialPoints.length > 0) {
        if (specialPoints.indexOf(edge.from) > -1 || specialPoints.indexOf(edge.to) > -1) {
          if (excludePoints.indexOf(edge.from) < 0 || excludePoints.indexOf(edge.to) < 0) {
            // 如果边的一端 不在 excludePoints 数组中，另一端在specialPoints 数组中， 也需要保留
            restEdges.push(edge)
          }
        }
      }
    })
    restEdges2.push(restEdges)
  })
  return restEdges2
}

// 求两线段的交点
function segmentsCross(p1, p2, q1, q2) {
  if (p1 === q1 || p1 === q2) {
    return p1
  }
  if (p2 === q1 || p2 === q2) {
    return p2
  }
  const cross = getCrossPoint(p1, p2, q1, q2)
  if (cross == null) {
    // the two line is parallel
    if (getPointOnVectorSide(p1, p2, q1) === ON_LINE_IN) {
      return q1
    }
    if (getPointOnVectorSide(p1, p2, q2) === ON_LINE_IN) {
      return q2
    }
    return null
  }

  if (isBetween(cross.x, p1.x, p2.x) && isBetween(cross.x, q1.x, q2.x) &&
    isBetween(cross.y, p1.y, p2.y) && isBetween(cross.y, q1.y, q2.y)) {
    const arr = [p1, p2, q1, q2]
    for (const pt of arr) {
      if (equals(pt, cross, true)) {
        return pt
      }
    }
    return cross
  }
  return null
}

// 两条直线的四点共线时，求交点
function specialSegmentCross(p0, p1, q0, q1) {
  const target = []
  const flag0 = getPointOnVectorSide(p0, p1, q0)
  const flag1 = getPointOnVectorSide(p0, p1, q1)
  const arr = [ON_LINE_OUT, ON_LINE_IN]
  if (arr.indexOf(flag0) < 0 || arr.indexOf(flag1) < 0) {
    return target
  }
  const pBox = findBox2([p0, p1])
  if (pBox.contain(q1)) {
    target.push(q1)
  }
  if (pBox.contain(q0)) {
    target.push(q0)
  }
  const qBox = findBox2([q0, q1])
  if (qBox.contain(p1)) {
    target.push(p1)
  }
  if (qBox.contain(p0)) {
    target.push(p0)
  }
  return target
}

/**
 * 如果两个轮廓，有相同坐标的顶点，则使它们的数组共有一个顶点对象
 * @param {{x: number, y: number}[]} vertices0
 * @param {{x: number, y: number}[]} vertices1
 * @return {number} 共用的顶点数目
 */
function mergeVertices(vertices0, vertices1) {
  const map = []; let mergeCount = 0
  for (let i = 0; i < vertices0.length; i++) {
    for (let j = 0; j < vertices1.length; j++) {
      if (!map[j] && equals(vertices1[j], vertices0[i])) {
        vertices1[j] = vertices0[i]
        vertices1[j].shared = true
        map[j] = 1
        mergeCount++
      }
    }
  }
  if (equals(vertices1[0], vertices1[vertices1.length - 1])) {
    vertices1[vertices1.length - 1] = vertices1[0]
    vertices1[0].sharedBySelf = true
  }
  return mergeCount
}

function getValidIndex(index, total) {
  if (index >= total) {
    return index % total
  }
  if (index < 0) {
    return total + index % total
  }
  return index
}

// return true if number m is between a and b
function isBetween(m, a, b) {
  if (m >= a && m <= b) {
    return true
  }
  if (m >= b && m <= a) {
    return true
  }
  const ma = Math.abs(m - a); const mb = Math.abs(m - b)
  if (ma <= minimum || mb <= minimum) {
    return true
  }
  return false
}

// 求两直线的交点
function getCrossPoint(start1, end1, start2, end2) {
  const a1 = end1.y - start1.y
  const b1 = start1.x - end1.x
  const c1 = end1.x * start1.y - start1.x * end1.y
  const a2 = end2.y - start2.y
  const b2 = start2.x - end2.x
  const c2 = end2.x * start2.y - start2.x * end2.y
  const denominator = (a2 * b1 - a1 * b2)
  if (denominator === 0) {
    return null
  }
  const x = (b2 * c1 - b1 * c2) / denominator
  const y = (a1 * c2 - a2 * c1) / denominator
  return {x: x, y: y}
}

// 求线段和直线的交点
function getLineSegmentCrossPoint(lineStart, lineEnd, segmentStart, segmentEnd) {
  const crossPoint = getCrossPoint(lineStart, lineEnd, segmentStart, segmentEnd)
  if (!crossPoint) {
    return null
  }
  if (isBetween(crossPoint.x, segmentStart.x, segmentEnd.x) && isBetween(crossPoint.y, segmentStart.y, segmentEnd.y)) {
    return crossPoint
  }
  return null
}

function getDistance(v1, v2) {
  return Math.sqrt(getDistanceSquare(v1, v2))
}

function getDistanceSquare(v1, v2) {
  const dx = v2.x - v1.x
  const dy = v2.y - v1.y
  return dx * dx + dy * dy
}

function getAngleWithX_axis(v1, v2) {
  const distance = getDistance(v1, v2)
  const dx = v2.x - v1.x
  const cosA = dx / distance
  if (v2.y >= v1.y) {
    return Math.acos(cosA)
  } else {
    return 2 * Math.PI - Math.acos(cosA)
  }
}

function getAngle(a, b, c) {
  const a1 = getAngleWithX_axis(b, a)
  const a2 = getAngleWithX_axis(b, c)
  const ret = Math.abs(a1 - a2)
  if (ret > Math.PI) {
    return Math.PI * 2 - ret
  } else {
    return ret
  }
}

function threePointInOneLine(v1, v2, v3) {
  if (v1.x === v2.x) {
    return v3.x === v2.x
  }
  if (v2.x === v3.x) {
    return v1.x === v2.x
  }
  const k12 = (v1.y - v2.y) / (v1.x - v2.x)
  const k23 = (v3.y - v2.y) / (v3.x - v2.x)
  return Math.abs(k12 - k23) < 0.0002
}

// return point p's position regards vector v1 to v2, use 3d right hand's coordinate system
function getPointOnVectorSide(v1, v2, p) {
  if (equals(v1, p) || equals(v2, p)) {
    return ON_LINE_IN
  }
  const v1_v2 = {x: v2.x - v1.x, y: v2.y - v1.y} // vector v1 to v2
  const v1_p = {x: p.x - v1.x, y: p.y - v1.y} // vector v1 to p
  const cross_product = v1_v2.x * v1_p.y - v1_p.x * v1_v2.y

  if (cross_product > EPS) {
    // return ON_RIGHT_SIDE;
    return ON_LEFT_SIDE
  } else if (cross_product < -EPS) {
    // return ON_LEFT_SIDE;
    return ON_RIGHT_SIDE
  } else {
    if (isBetween(p.x, v1.x, v2.x) && isBetween(p.y, v1.y, v2.y)) {
      return ON_LINE_IN
    }
    return ON_LINE_OUT
  }
}

function isClockwiseSquence(vertices) {
  let leftAngleSum = 0
  let rightAngleSum = 0
  for (let i = 0; i < vertices.length; i++) {
    const v2Index = getValidIndex(i + 1, vertices.length)
    const pIndex = getValidIndex(i + 2, vertices.length)
    if (threePointInOneLine(vertices[i], vertices[v2Index], vertices[pIndex])) {
      continue
    }
    const curSide = getPointOnVectorSide(vertices[i], vertices[v2Index], vertices[pIndex])
    const angle = Math.PI - getAngle(vertices[i], vertices[v2Index], vertices[pIndex])
    if (curSide === ON_LEFT_SIDE) {
      // vertices[v2Index].mark = 'left'
      leftAngleSum += angle
    } else if (curSide === ON_RIGHT_SIDE) {
      // vertices[v2Index].mark = 'right'
      rightAngleSum += angle
    }
  }
  if (rightAngleSum === 0 && leftAngleSum === 0) {
    console.error('序列既不是顺时针，也不是逆时针的')
    console.log('vertices is invalid, all points on one line')
    return false
  }
  // Math.abs(rightAngleSum - leftAngleSum)/2 equal with Math.PI
  if (rightAngleSum > leftAngleSum) {
    return true
  }
  return false
}

// 去除 相邻的 重复顶点
function removeNearDuplicate(pointsCircle) {
  const target = []; let current = null
  for (const point of pointsCircle) {
    if (current == null || !equals(current, point)) {
      target.push(point)
      current = point
    }
  }
  if (equals(target[0], target[target.length - 1])) {
    target.pop()
  }
  return target
}

/**
 * 去除 毛刺点
 * @param {{x: number, y: number}[]} pointsCircle
 * @return {{x: number, y: number}[]}
 */
function removeRags(pointsCircle) {
  const map = {}; const keys = []
  for (let i = 0; i < pointsCircle.length; i++) {
    const point = pointsCircle[i]
    const key = point.x.toFixed(precision) + ',' + point.y.toFixed(precision)
    if (map[key] === undefined) {
      map[key] = [i]
    } else {
      map[key].push(i)
      if (keys.indexOf(key) < 0) {
        keys.push(key)
      }
    }
  }
  for (let i = keys.length - 1; i > -1; i--) {
    const key = keys[i]
    const start = map[key][0] + 1; const deleteCount = map[key][1] - map[key][0]
    if (deleteCount > 3) {
      continue // 避免数组首尾节点一样时 引发bug
    }
    const point = pointsCircle[start - 1]
    const key0 = point.x.toFixed(precision) + ',' + point.y.toFixed(precision)
    if (key0 === key) {
      pointsCircle.splice(start, deleteCount)
    }
  }
  return pointsCircle
}

/**
 * 精简 不带孔多边形的点序列, 如果顶点在多边形的边上则清除它
 * @param {{x: number, y: number}[]} pointsCircle
 * @return {{x: number, y: number}[]}
 */
function simplifyCircle(pointsCircle) {
  const keyPoints = []
  for (let i = 0; i < pointsCircle.length; i++) {
    let pre = i - 1; let nxt = i + 1
    if (pre < 0) {
      pre = pointsCircle.length - 1
    }
    if (nxt > pointsCircle.length - 1) {
      nxt = 0
    }
    const prePoint = pointsCircle[pre]
    const curPoint = pointsCircle[i]
    const nxtPoint = pointsCircle[nxt]
    const flag = getPointOnVectorSide(prePoint, nxtPoint, curPoint)
    if (flag !== ON_LINE_IN) {
      keyPoints.push(curPoint)
    }
  }
  return keyPoints
}

// 返回 二维点 的二维数组
function parseToCircles(verticesHoles, noSimplify) {
  const vecLst = verticesHoles[0];
  const holeIndices = verticesHoles[1]
  let circles = []; const circles2 = []
  if (holeIndices.length > 0) {
    for (let i = 0; i < holeIndices.length; i++) {
      let arr
      if (i === 0) {
        arr = vecLst.slice(0, holeIndices[i])
      } else {
        arr = vecLst.slice(holeIndices[i - 1], holeIndices[i])
      }
      circles.push(arr)
    }
    circles.push(vecLst.slice(holeIndices[holeIndices.length - 1], vecLst.length))
  } else {
    circles = [vecLst]
  }
  circles = circles.map(circle => removeNearDuplicate(circle))
  circles.forEach((circle, index) => {
    removeRags(circle)
    if (index === 0) {
      if (isClockwiseSquence(circle)) circle.reverse()
    } else {
      if (!isClockwiseSquence(circle)) circle.reverse()
    }
    if (!noSimplify) {
      circles2.push(simplifyCircle(circle))
    }
  })
  return noSimplify ? circles : circles2
}

/**
 * 设置每个Edge的 splitBy 属性，为拆分边做准备
 * @param {Edge[]} edges0
 * @param {Edge[]} edges1
 * @return {boolean}
 */
function splitTwoEdges(edges0, edges1) {
  const crossLst = []
  for (let i = 0; i < edges0.length; i++) {
    const a = edges0[i]
    for (let j = 0; j < edges1.length; j++) {
      const b = edges1[j]
      const cross = segmentsCross(a.from, a.to, b.from, b.to)
      if (cross == null) {
        continue
      }

      let pt = a.addSplitBy(cross)
      if (pt) { crossLst.push(pt) }
      pt = b.addSplitBy(cross)
      if (pt) { crossLst.push(pt) }
    }
  }
  return crossLst.length > 0
}

/**
 * 返回true 表示两个多边形轮廓的线段之间有交点
 * @param {Edge[][]} edges4Circles0
 * @param {Edge[][]} edges4Circles1
 * @return {boolean}
 */
function splitEdgesOfCircles(edges4Circles0, edges4Circles1) {
  let mergeSuccess = false
  for (const edges0 of edges4Circles0) {
    for (const edges1 of edges4Circles1) {
      const splited = splitTwoEdges(edges0, edges1)
      mergeSuccess = mergeSuccess || splited
    }
  }
  return mergeSuccess
}

/**
 * @param {{x: number, y: number}[][]} circles
 * @param {number} polygonIndex
 * @return {Edge[][]}
 */
function createEdges4Circles(circles, polygonIndex) {
  const edges2 = []
  let count = 0
  for (const circle of circles) {
    const edges = createEdges(circle, polygonIndex, count++)
    edges2.push(edges)
  }
  return edges2
}

function createEdges(vertices, polygonIndex, holeId) {
  const edges = []
  let i
  for (i = 0; i < vertices.length; i++) {
    if (i === vertices.length - 1) {
      edges[i] = new Edge(vertices[i], vertices[0], polygonIndex, holeId || 0)
    } else {
      edges[i] = new Edge(vertices[i], vertices[i + 1], polygonIndex, holeId || 0)
    }
  }

  return edges
}

/**
 * 根据 Edge 的 splitBy 属性把线段拆分为多段
 * @param {Edge} edge
 * @return {Edge[]}
 */
function processSplitBy(edge) {
  if (edge.splitBy.length === 0) {
    return [edge]
  }
  const distanceSqs = []
  edge.splitBy.forEach(it => distanceSqs.push(getDistanceSquare(edge.from, it)))
  const distanceSqsSorted = distanceSqs.slice().sort((a, b) => a - b)
  let from = edge.from; let to
  const splited = []
  for (let i = 0; i < distanceSqsSorted.length; i++) {
    const index = distanceSqs.indexOf(distanceSqsSorted[i])
    to = edge.splitBy[index]
    // if (from.x == to.x && from.y == to.y) {
    //     console.log("strange edge 0 found");
    // }
    splited.push(new Edge(from, to, edge.belong, edge.holeId))
    from = to
  }
  splited.push(new Edge(to, edge.to, edge.belong, edge.holeId))
  return splited
}

/**
 * @param {Edge[][]} edges20
 * @param {Edge[][]} edges21
 * @param {{x: number, y: number}[][][]} polygons20
 * @param {{x: number, y: number}[][][]} polygons21
 * @param {string} boolType
 */
function removeEdges(edges20, edges21, polygons20, polygons21, boolType) {
  const holeEdges0 = [];
  const holeEdges1 = []
  edges20.forEach(edges => holeEdges0.push(...edges))
  edges21.forEach(edges => holeEdges1.push(...edges))

  const len0 = holeEdges0.length; const len1 = holeEdges1.length
  if (holeEdges0.length > 0 && holeEdges1.length > 0) {
    removeOutlineEdges(holeEdges0, holeEdges1, polygons20, polygons21, boolType)
    if (len0 > holeEdges0.length) {
      edges20.forEach(edges => arrAonB(edges, holeEdges0))
    }
    if (len1 > holeEdges1.length) {
      edges21.forEach(edges => arrAonB(edges, holeEdges1))
    }
  }
}

/**
 * @param {Edge[]} outline0 既是输入也是输出，如果其中的边在 polygons21 中，则删除它
 * @param {Edge[]} outline1 既是输入也是输出，如果其中的边在 polygons20 中，则删除它
 * @param {{x: number, y: number}[][][]} polygons20
 * @param {{x: number, y: number}[][][]} polygons21
 * @param {string} boolType
 */
function removeOutlineEdges(outline0, outline1, polygons20, polygons21, boolType = bool_union) {
  const edge0in1 = [];
  const edge1in0 = []
  const edge0notIn1 = [];
  const edge1notIn0 = []
  const edges = outline0.concat(outline1)
  for (let i = 0; i < edges.length; i++) {
    const edge = edges[i]
    if (edge.getChecked()) {
      continue
    }
    const polygons2 = edge.belong === 0 ? polygons21 : polygons20
    const isIn = isPointInPolygonWithHoles(edge.getMidPoint(), polygons2)
    if (isIn) {
      edge.belong === 0 ? edge0in1.push(edge) : edge1in0.push(edge)
    } else {
      edge.belong === 0 ? edge0notIn1.push(edge) : edge1notIn0.push(edge)
    }
  }

  if (boolType === bool_union || boolType === bool_a_sub_b) {
    if (edge0in1.length > 0) {
      arrAsubB(outline0, edge0in1)
    }
  }
  if (boolType === bool_union) {
    if (edge1in0.length > 0) {
      arrAsubB(outline1, edge1in0)
    }
  } else if (boolType === bool_a_sub_b) {
    if (edge1notIn0.length > 0) {
      arrAsubB(outline1, edge1notIn0)
    }
  }
  if (boolType === bool_intersection) {
    outline0.splice(0, outline0.length)
    outline1.splice(0, outline1.length)
    outline0.push(...edge0in1)
    outline1.push(...edge1in0)
  }
}

/**
 * 针对特殊情况的处理，当个两个图形边互相重叠时，删除共享边，有两种共享边，相叠 与 不相叠
 * 相叠, 边1 {from: a, to: b}, 边2 {from: a, to: b}, 这时只删除 边1 或者 边2
 * 不相叠, 边1 {from: a, to: b}, 边2 {from: b, to: a}, 这时边1 和 边2都需要删除
 * @param {Edge[][]} edges20
 * @param {Edge[][]} edges21
 */
function removeOverlapEdges(edges20, edges21) {
  for (const edges0 of edges20) {
    for (const edges1 of edges21) {
      removeOverlapOutlineEdges(edges0, edges1)
    }
  }
  const empty0 = edges20.filter(edges => edges.length === 0)
  const empty1 = edges21.filter(edges => edges.length === 0)
  if (empty0.length > 0) { arrAsubB(edges20, empty0) }
  if (empty1.length > 0) { arrAsubB(edges21, empty1) }
}

/**
 *
 * @param {Edge[]} outline0
 * @param {Edge[]} outline1
 */
function removeOverlapOutlineEdges(outline0, outline1) {
  const sharedEdges0 = []; const sharedEdges1 = []
  for (let i = 0; i < outline0.length; i++) {
    const edge0 = outline0[i]
    let j = 0
    for (; j < outline1.length; j++) {
      const edge1 = outline1[j]
      const obj = edge0.sameSource(edge1)
      if (obj) {
        if (obj.similarType === 3) { // 异向，同端点
          sharedEdges0.push(edge0)
          sharedEdges1.push(edge1)
        } else { // 同向，同端点；
          sharedEdges0.push(edge0)
          edge1.setChecked()
        }
        break
      }
    }
  }
  if (sharedEdges0.length > 0) {
    arrAsubB(outline0, sharedEdges0)
    arrAsubB(outline1, sharedEdges1)
  }
}

// 返回被至少四条边共用的顶点，针对可能合并出半环的特殊情况
function findSpecialPoints(edges) {
  const map = {}; const target = []
  for (const edge of edges) {
    addSpecialPoint(map, edge.from, target)
    addSpecialPoint(map, edge.to, target)
  }
  return target
}
function addSpecialPoint(map, point, target) {
  const pointId = point.x + ', ' + point.y
  if (map[pointId] === undefined) {
    map[pointId] = 1
  } else {
    map[pointId]++
  }
  if (map[pointId] > 3 && target.indexOf(point) < 0) {
    target.push(point)
  }
}

/**
 * @param {Edge[][]} edges4Circles
 * @return {{x: number, y: number}[][]}
 */
function edgesLst2PointsCircles(edges4Circles) {
  const pointsCircles = []
  edges4Circles.forEach((edges, index) => {
    pointsCircles.push(edges2Points(edges))
    edges.forEach(edge => (edge.holeId = index))
  })
  return pointsCircles
}

// -----------triangle start--------------------
function splitArray(vertices, index1, index2) {
  const small = Math.min(index1, index2)
  const big = Math.max(index1, index2)
  const v1 = vertices[small]
  const v2 = vertices[big]
  let start = small + 1
  const numbersBetween = Math.abs(index1 - index2) - 1
  const delta = start + numbersBetween - vertices.length
  if (delta > 0) {
    console.error('splitArray, attention! how is it possible to go here')
    for (let i = 0; i < delta; i++) {
      const item = vertices.shift()
      vertices.push(item)
      start--
    }
  }
  const newSeries = vertices.splice(start, numbersBetween)
  newSeries.push(v2, v1)
  return [newSeries, vertices]
}

// 如果线段[ vertices[index]， vertices[checkingIndex] ] 和 vertices中的任意边相交，返回true
function isCrossWithEdges(vertices, index, checkingIndex) {
  const q1 = getValidIndex(checkingIndex - 1, vertices.length)
  const q2 = getValidIndex(checkingIndex + 1, vertices.length)
  const p1 = getValidIndex(index - 1, vertices.length)
  const p2 = getValidIndex(index + 1, vertices.length)
  const needSkip1 = [p1, index, p2]
  const needSkip2 = [q1, checkingIndex, q2]
  for (let i = 0; i < vertices.length; i++) {
    const edgeIndex = (i + 1) % vertices.length
    if (needSkip1.indexOf(i) >= 0 && needSkip1.indexOf(edgeIndex) >= 0) {
      continue
    }
    if (needSkip2.indexOf(i) >= 0 && needSkip2.indexOf(edgeIndex) >= 0) {
      continue
    }
    if (segmentsCross(vertices[i], vertices[edgeIndex], vertices[index], vertices[checkingIndex])) {
      return true
    }
  }
  return false
}

/**
 * 判断二维点在 是否凸多边形内部（包含边）
 * @param {{x: number, y: number}} point 二维点
 * @param {{x: number, y: number}[]} vertexLst 逆时钟序列的轮廓
 * @return {boolean}
 */
function isInConvex(point, vertexLst) {
  let vertices = vertexLst
  if (isClockwiseSquence(vertexLst)) {
    vertices = vertexLst.slice().reverse()
  }
  let i
  for (i = 0; i < vertices.length - 1; i++) {
    const side = getPointOnVectorSide(vertices[i], vertices[i + 1], point)
    if (side === ON_LINE_IN) {
      return true
    }
    if (side !== ON_LEFT_SIDE) {
      return false
    }
  }
  const side = getPointOnVectorSide(vertices[i], vertices[0], point)
  if (side === ON_LEFT_SIDE || side === ON_LINE_IN) {
    return true
  }
  return false
}

/**
 * @param {{x: number, y: number}} point
 * @param {{x: number, y: number}[][]} convexPolygons
 * @return {boolean}
 */
function isInConvexPolygons(point, convexPolygons) {
  for (let i = 0; i < convexPolygons.length; i++) {
    const convex = convexPolygons[i]
    if (isInConvex(point, convex)) return true
  }
  return false
}

/**
 * 判断二维点point 是否在带孔多边形内部，convexPolygons2 是二维数组 其中每个元素为凸多边形顶点列表，内容格式如下
 * [多边形最外层剖分为 n个凸多边形的列表, 多边形第一个孔剖分为 n个凸多边形的列表, ...多边形第n个孔剖分为 n个凸多边形的列表]
 * @param {{x: number, y: number}} point
 * @param {{x: number, y: number}[][][]} convexPolygons2
 * @return {boolean}
 */
function isPointInPolygonWithHoles(point, convexPolygons2) {
  const outestPolygons = convexPolygons2[0]
  const isInOutestCircle = isInConvexPolygons(point, outestPolygons)
  if (!isInOutestCircle || convexPolygons2.length === 1) {
    return isInOutestCircle
  }
  for (let i = 1; i < convexPolygons2.length; i++) {
    const convexPolygonsOfHole = convexPolygons2[i]
    const isInHole = isInConvexPolygons(point, convexPolygonsOfHole)
    if (isInHole) {
      return false
    }
  }
  return true
}

/**
 * 凹多边形 转换为若干个凸多边形
 * @param {{x: number, y: number}[]} vertices 凹多边形的顶点轮廓
 * @param {{x: number, y: number}[][]} output
 */
function concavToConvex(vertices, output) {
  // let points = filterOutUselessVertex(vertices);
  const points = vertices.slice()
  const total = points.length
  const isClockwise = isClockwiseSquence(points)
  let concavPoint = null
  let concavIndex = -1
  for (let i = 0; i < total; i++) { // 寻找凹点的索引
    const v0 = points[i]
    const v1 = points[getValidIndex(i + 1, total)]
    const v2 = points[getValidIndex(i + 2, total)]
    if (threePointInOneLine(v0, v1, v2)) {
      continue
    }
    const curSide = getPointOnVectorSide(v0, v1, v2)
    if (isClockwise && curSide === ON_LEFT_SIDE) {
      concavPoint = v1
      concavIndex = getValidIndex(i + 1, total)
      break
    } else if (!isClockwise && curSide === ON_RIGHT_SIDE) {
      concavPoint = v1
      concavIndex = getValidIndex(i + 1, total)
      break
    }
  }
  if (concavPoint != null) {
    const index = concavIndex
    const p2 = getValidIndex(index + 1, total)
    const p1 = getValidIndex(index - 1, total)
    const angle = getAngle(points[p1], points[index], points[p2])
    const halfAngle = (Math.PI * 2 - angle) / 2
    let minAngle = 100
    let divideIndex
    for (let i = 0; i < total; i++) {
      if (i === index || i === p1 || i === p2) {
        continue
      }
      const side = getPointOnVectorSide(points[p1], points[index], points[i])
      if ((isClockwise && side === ON_RIGHT_SIDE) ||
        (!isClockwise && side === ON_LEFT_SIDE) ||
        side === ON_LINE_OUT) {
        if (!isCrossWithEdges(points, index, i)) {
          const curAngle = getAngle(points[p1], points[index], points[i])
          const delta = Math.abs(curAngle - halfAngle)
          if (delta < minAngle) {
            minAngle = delta
            divideIndex = i
          }
        }
      }
    }
    if (divideIndex === undefined) {
      console.error('error! found in concavToConvex() ')
      return
    }
    const arr = splitArray(points, index, divideIndex)
    concavToConvex(arr[0], output)
    concavToConvex(arr[1], output)
  } else {
    output.push(points)
  }
}
// -----------triangle end----------------------
// -----------ear cut start---------------------------
function isBetween0(m, a, b) {
  if (Math.abs(m - a) <= minimum || Math.abs(m - b) <= minimum) {
    return BETWEEN_ON // m 和 a 或 b 过于接近，则认为 m == a 或 m == b
  }
  return ((m > a && m < b) || (m > b && m < a)) ? BETWEEN_IN : BETWEEN_NOT
}
function isBetween2(m, a, b) {
  const target = isBetween0(m, a, b)
  return target === BETWEEN_ON || target === BETWEEN_IN
}
function isBetween3(m, a, b, countBounds = true) {
  let a0 = a; let b0 = b
  if (a > b) {
    a0 = b
    b0 = a
  }
  const target = isBetween0(m, a0, b0)
  if (countBounds) {
    return target === BETWEEN_ON || target === BETWEEN_IN
  } else {
    return target === BETWEEN_IN
  }
}
// 求以point为起点，竖直向上的射线和线段（p1, p2）的交点
function rayUpSegmentCross(point, p1, p2) {
  if (point.y > p1.y + minimum && point.y > p2.y + minimum) {
    return null
  }

  let small, big
  if (p1.x > p2.x) {
    small = p2
    big = p1
  } else {
    small = p1
    big = p2
  }
  const res = isBetween0(point.x, small.x, big.x)
  if (res === BETWEEN_NOT) {
    return null
  } else if (res === BETWEEN_ON) {
    if (p1.x === p2.x) {
      if (small.y >= point.y - minimum) {
        return [small, big]
      } else if (big.y > point.y - minimum) {
        return [point]
      } else {
        return null
      }
    } else if (p1.x === point.x) {
      return [p1]
    } else {
      return [p2]
    }
  } else { // res == BETWEEN_IN
    const rate = (point.x - small.x) / (big.x - small.x) // lerp alpha
    const dx = big.x - small.x
    const dy = big.y - small.y
    const cross = {x: small.x + dx * rate, y: small.y + dy * rate}
    if (cross.y >= point.y - minimum) { // ? cross.y === point.y
      return [cross]
    }
    return null
  }
}

// 耳切法  如果 点 正好在某条边上，返回false
function isPointInEdges(point, edges) {
  const target = isPointInEdges0(point, edges)
  return target === POLYGON_INSIDE
}

/**
 * @param {{x: number, y: number}} point
 * @param {Edge[]} edges
 * @return {number}
 */
function isPointInEdges0(point, edges) {
  const crossedPoints = []
  const checked = []
  for (let i = 0; i < edges.length; i++) {
    const edge = edges[i]
    if (checked.indexOf(edge) >= 0) {
      continue
    }
    const arr = rayUpSegmentCross(point, edge.from, edge.to)
    if (!arr) {
      continue
    }

    let prev = i - 1; let next = i + 1
    if (prev < 0) {
      prev = edges.length - 1
    }
    if (next > edges.length - 1) {
      next = 0
    }
    if (arr.length === 1) {
      const pt = arr[0]
      if (equals(point, pt, true)) {
        return POLYGON_ON_EDGE
      }
      if (pt !== edge.from && pt !== edge.to) {
        crossedPoints.push(pt)
      } else if (pt === edge.to) {
        let edgeNext = edges[next]
        checked.push(edgeNext)
        if (edgeNext.vertical()) {
          if (isBetween3(point.y, edgeNext.from.y, edgeNext.to.y)) {
            return POLYGON_ON_EDGE
          }
          next += 1
          if (next > edges.length - 1) {
            next = 0
          }
          edgeNext = edges[next]
          checked.push(edgeNext)
        }
        if (isBetween3(point.x, edge.from.x, edgeNext.to.x, false)) {
          crossedPoints.push(pt)
        }
      } else { // pt == edge.from
        let edgePrev = edges[prev]
        checked.push(edgePrev)
        if (edgePrev.vertical()) {
          if (isBetween3(point.y, edgePrev.from.y, edgePrev.to.y)) {
            return POLYGON_ON_EDGE
          }
          prev -= 1
          if (prev < 0) {
            prev = edges.length - 1
          }
          edgePrev = edges[prev]
          checked.push(edgePrev)
        }
        if (isBetween3(point.x, edgePrev.from.x, edge.to.x, false)) {
          crossedPoints.push(pt)
        }
      }
    } else if (arr.length === 2) {
      const edgeNext = edges[next]
      const edgePrev = edges[prev]
      if (isBetween2(point.y, arr[0], arr[1])) {
        return POLYGON_ON_EDGE
      }
      if (isBetween3(point.x, edgePrev.from.x, edgeNext.to.x, false)) {
        crossedPoints.push(arr[0])
      }
    }
  }
  return crossedPoints.length % 2 === 1 ? POLYGON_INSIDE : POLYGON_OUTSIDE
}
// -----------ear cut end---------------------------
/**
 * 返回三维数组，其中每个二维数组代表一个带孔多边形
 * @param {Edge[][]} splited0
 * @param {Edge[][]} splited1
 * @param {{x: number, y: number}[][]} circles0
 * @param {{x: number, y: number}[][]} circles1
 * @param {string} boolType
 * @return {{x: number, y: number}[][][]|[]}
 */
function findCircles(splited0, splited1, circles0, circles1, boolType) {
  const outestCircles = []
  const polygons20 = []
  const polygons21 = []
  circles0.forEach(circle => {
    const polygons = []
    concavToConvex(circle, polygons)
    polygons20.push(polygons)
  })
  circles1.forEach(circle => {
    const polygons = []
    concavToConvex(circle, polygons)
    polygons21.push(polygons)
  })

  removeOverlapEdges(splited0, splited1)
  if (splited0.length === 0 || splited1.length === 0) {
    const edges4Circles = splited0.concat(splited1)
    return edgesLst2PointsCircles(edges4Circles)
  }
  removeEdges(splited0, splited1, polygons20, polygons21, boolType)

  const outlineEdgesA = splited0[0].slice()
  const outlineEdgesB = splited1[0].slice()
  let outlineEdgesA2 = []
  const excludePoints = []
  splited0.forEach(arr => outlineEdgesA2 = outlineEdgesA2.concat(arr))
  while (outlineEdgesA.length > 0) {
    const outestCircle = []
    const usedEdges = []
    const startEdge = findStartEdge(outlineEdgesA, outlineEdgesB)
    let curEdge = startEdge
    usedEdges.push(curEdge)
    outestCircle.push(startEdge.from)
    while (curEdge.to !== startEdge.from) {
      const curEdge0 = curEdge
      if (boolType === bool_a_sub_b) { // A - B求差集时，可能破坏孔结构
        curEdge = findNextEdge(curEdge0, outlineEdgesA2, outlineEdgesB)
      } else {
        curEdge = findNextEdge(curEdge0, outlineEdgesA, outlineEdgesB)
      }
      usedEdges.push(curEdge)
      if (outestCircle.indexOf(curEdge.from) > -1) {
        console.error('Error! findCircles() dead loop in.')
        return [] // 避免死循环
      }
      outestCircle.push(curEdge.from)
    }
    arrAsubB(outlineEdgesA, usedEdges)
    arrAsubB(outlineEdgesB, usedEdges)
    outestCircles.push(outestCircle)
    outestCircle.forEach(it => excludePoints.push(it))
  }

  let pointsSharedByCircles = []
  if (boolType === bool_union) {
    pointsSharedByCircles = findSpecialPoints(splited0[0].concat(splited1[0]))
  }
  const restEdges0 = getRestEdges(splited0, excludePoints, pointsSharedByCircles)
  const restEdges1 = getRestEdges(splited1, excludePoints, pointsSharedByCircles)
  const holes = []
  if (boolType === bool_union) {
    while (outestCircles.length > 1) {
      holes.push(outestCircles.pop())
    }
  }
  findHoles(restEdges0, restEdges1, holes)
  if (outestCircles.length === 1) {
    let graphics = []
    let realHoles = holes
    if (boolType === bool_a_sub_b) {
      const obj = analyseHolesContain(holes)
      realHoles = obj.holes
      graphics = obj.graphics
    }
    const outestPoints = outestCircles[0]
    return [[outestPoints].concat(realHoles)].concat(graphics)
  } else {
    const polygons = []
    outestCircles.forEach((circle, index) => {
      polygons.push({pointsArr: [circle], outlineEdges: createEdges(circle, index, 0)})
    })
    for (let i = 0; i < holes.length; i++) {
      const hole = holes[i]
      for (let j = 0; j < polygons.length; j++) {
        const polygonObj = polygons[j]
        const holePoint = {x: (hole[0].x + hole[1].x) * 0.5, y: (hole[0].y + hole[1].y) * 0.5}
        if (isPointInEdges(holePoint, polygonObj.outlineEdges)) {
          polygonObj.pointsArr.push(hole)
          break
        }
      }
    }
    const target = polygons.map(it => it.pointsArr)
    return target
  }
}

/**
 * 分析孔 与 孔之间嵌套关系
 * @param srcHoles {{x: number, y: number}[][]}
 * @return {holes: [], graphics: []}
 */
function analyseHolesContain(srcHoles) {
  const holesObjs = srcHoles.map((it, index) => {
    return {hole: it, edges: createEdges(it, index, 0), contains: [], containBy: []}
  })
  const containedSet = new Set()
  for (let i = 0; i < holesObjs.length; i++) {
    const holeA = holesObjs[i]
    for (let j = i + 1; j < holesObjs.length; j++) {
      const holeB = holesObjs[j]
      if (isPointInEdges(holeA.hole[0], holeB.edges)) {
        holeB.contains.push(holeA)
        holeA.containBy.push(holeB)
        containedSet.add(holeA)
      } else if (isPointInEdges(holeB.hole[0], holeA.edges)) {
        holeA.contains.push(holeB)
        holeB.containBy.push(holeA)
        containedSet.add(holeB)
      }
    }
  }
  const containedArr = [...containedSet]
  const containedHoles = containedArr.map(it => it.hole)
  const realHoleObjs = arrAsubB(holesObjs, containedArr)
  const holes = arrAsubB(srcHoles.slice(), containedHoles) // 元素为真正的孔 2d坐标的一维数组
  const graphics = [] // 元素为可能包含若干个孔的图形 2d坐标的二维数组
  containedArr.forEach(holeObj => arrAsubB(holeObj.containBy, realHoleObjs))
  containedArr.forEach(holeObj => {
    if (holeObj.containBy.length) {
      return
    }
    const arr = [holeObj.hole]
    holeObj.contains.forEach(obj => {
      arr.push(obj.hole)
    })
    graphics.push(arr)
  })
  return {holes, graphics}
}

/**
 * true 顶点是 在 带孔多边形中
 * @param {{x: number, y: number}} point
 * @param {Edge[][]} edges4Circles
 */
function isPointInEdges4Circles(point, edges4Circles) {
  const contour = edges4Circles[0]
  const holes = edges4Circles.slice(1)
  if (!isPointInEdges(point, contour)) {
    return false // 在边上，也不算是在多边形内部
  }
  const inHole = holes.find(hole => {
    const flag = isPointInEdges0(point, hole)
    return flag === POLYGON_INSIDE || flag === POLYGON_ON_EDGE
  })
  return !inHole
}

function copyVerticesHoles(verticesHoles) {
  return [verticesHoles[0].map(it => {
    return {x: it.x, y: it.y}
  }), verticesHoles[1]]
}
/**
 * 对带孔二维多边形做布尔运算
 * @param {{x: number, y: number}[][]} verticesHolesA0 最外轮廓是逆时针序列，孔是顺时针序列
 * @param {{x: number, y: number}[][]} verticesHolesB0 最外轮廓是逆时针序列，孔是顺时针序列
 * @param {string} boolType
 * @return {*[]} 返回三维数组，每个元素的结构类似于 [[v0, v1, v3, v4, v5, m0, m1, m2, n0, n1, n2, n3], [6, 9]]
 * 注意：两个图形的轮廓线不相交，并且不存在 a包含b 或者b包含a的情况，求差集时 返回 [verticesHolesA]，求并集和交集时返回空数组
 */
function boolPolygons(verticesHolesA0, verticesHolesB0, boolType) {
  // processPrecision(verticesHolesA[0], verticesHolesB[0])
  const verticesHolesA = copyVerticesHoles(verticesHolesA0)
  const verticesHolesB = copyVerticesHoles(verticesHolesB0)
  verticesHolesA[0].forEach(point => point.shared = undefined);
  verticesHolesB[0].forEach(point => point.shared = undefined);
  const map = mergeVertices(verticesHolesA[0], verticesHolesB[0])
  const sharedCount = verticesHolesB[0].filter(it => it.shared).length
  const circlesA = parseToCircles(verticesHolesA)
  const circlesB = parseToCircles(verticesHolesB)
  if (boolType === bool_a_sub_b) {
    circlesB.forEach(circle => circle.reverse())
  }
  const edges4CirclesA = createEdges4Circles(circlesA, 0)
  const edges4CirclesB = createEdges4Circles(circlesB, 1)
  const mergeSuccess = splitEdgesOfCircles(edges4CirclesA, edges4CirclesB)

  if (!mergeSuccess && sharedCount < 2) { // 两个图形的轮廓线不相交
    const outlineA = circlesA[0]
    const outlineB = circlesB[0]
    const edgesA = createEdges(outlineA, 0, 0)
    const edgesB = createEdges(outlineB, 1, 0)
    for (let i = 0; i < outlineB.length; i++) {
      const target = isPointInEdges0(outlineB[i], edgesA)
      if (target === POLYGON_OUTSIDE) {
        break
      } else if (target === POLYGON_INSIDE) { // polygon B totally inside polygon A
        // holesInAandB 保存 原本属于 A的孔洞，后来发现同时也属于 B
        const holesInAandB = circlesA.filter((circle, index) => {
          if (index === 0) {
            return false
          }
          const flag = isPointInEdges0(circle[0], edges4CirclesB[0])
          return flag === POLYGON_INSIDE // 属于 A的孔洞也完成包含在 B的最外轮廓中
        })
        if (boolType === bool_union) {
          // 原本属于 B 的孔洞 现在也属于 A了
          const circleLstA = circlesA.concat(circlesB.slice(1))
          return [formatCircles(circleLstA)]
        } else if (boolType === bool_intersection) {
          const bCircles = circlesB.filter((circle, index) => {
            if (index === 0) {
              return true
            }
            return isPointInEdges4Circles(circle[0], edges4CirclesA) // true： B中的孔没有被 A中的孔包含
          })
          bCircles.push(...holesInAandB)
          return [formatCircles(bCircles)]
        } else if (boolType === bool_a_sub_b) {
          const aCircles = circlesA.filter(circle => !holesInAandB.includes(circle))
          aCircles.push(outlineB) // 所有属于 A 又属于 B的孔被 B的最外轮廓替换
          const target = [formatCircles(aCircles)]
          // 保存只属于B的孔
          circlesB.forEach((circle, index) => {
            if (index === 0) {
              return
            }
            const holeOnlyBelongB =  isPointInEdges4Circles(circle[0], edges4CirclesA)
            if (!holeOnlyBelongB) {
              return
            }
            // 只属于 B的孔 从 A上 挖去部分区域
            target.push(formatCircles([circle]))
          })
          return target
        }
      }
    }

    for (let i = 0; i < outlineA.length; i++) {
      const target = isPointInEdges0(outlineA[i], edgesB)
      if (target === POLYGON_OUTSIDE) {
        break
      } else if (target === POLYGON_INSIDE) { // polygon A totally inside polygon B
        if (boolType === bool_union) {
          return [verticesHolesB]
        } else if (boolType === bool_intersection) {
          return [verticesHolesA]
        } else if (boolType === bool_a_sub_b) {
          return []
        }
      }
    }
    // 两个图形的轮廓线不相交，并且不存在 a包含b 或者b包含a的情况
    if (boolType === bool_a_sub_b) {
      return [verticesHolesA]
    }
    return []
  }
  const splited0 = []; const splited1 = []
  edges4CirclesA.forEach(edges4Circle => {
    const arr = []
    edges4Circle.forEach(edge => arr.push(...processSplitBy(edge)))
    splited0.push(arr)
  })
  edges4CirclesB.forEach(edges4Circle => {
    const arr = []
    edges4Circle.forEach(edge => arr.push(...processSplitBy(edge)))
    splited1.push(arr)
  })
  const outlineAndHolesLst = findCircles(splited0, splited1, circlesA, circlesB, boolType)
  const target = []
  for (let j = 0; j < outlineAndHolesLst.length; j++) {
    const outlineAndHoles = outlineAndHolesLst[j]
    target.push(formatCircles(outlineAndHoles))
  }
  return target
}

/**
 * 把二维数组顶点数组 格式化为 [顶点列表， 索引列表], parseToCircles的反函数
 * @param {{x: number, y: number}[][]} circles
 * @return {[{x: number, y: number}[], number[]]}
 */
function formatCircles(circles) {
  const holeIndices = []
  let allVertices = []
  circles.forEach((it, index) => {
    const simplified = simplifyCircle(it)
    circles[index] = simplified
    allVertices = allVertices.concat(simplified)
  })
  if (circles.length > 1) {
    let curHoleIndex = 0
    for (let i = 1; i < circles.length; i++) {
      const len = circles[i - 1].length
      curHoleIndex += len
      holeIndices.push(curHoleIndex)
    }
  }
  allVertices = allVertices.map(it => {
    return {x: it.x, y: it.y}
  })
  return [allVertices, holeIndices]
}

// vertices0 vertices1 要求都是返回数据格式的顶点序列
// 可能返回一个带孔图形，例如：已知合并后的最外轮廓的逆时钟序列（v0, v1, v3, v4, v5)
// 孔1的顺时钟序列（m0, m1, m2), 孔2的顺时钟序列（n0, n1, n2, n3)
// 最终返回 二维数组 [[v0, v1, v3, v4, v5, m0, m1, m2, n0, n1, n2, n3], [6, 9]]
function mergeTwoPolygons(verticesHolesA, verticesHolesB) {
  const target = boolPolygons(verticesHolesA, verticesHolesB, bool_union)
  return target.length > 0 ? target[0] : target
}

function polygonAintersectB(verticesHolesA, verticesHolesB) {
  return boolPolygons(verticesHolesA, verticesHolesB, bool_intersection)
}

function mergePolygons(verticesHolesArr) {
  const wait4Merge = verticesHolesArr.slice()
  const merged = []
  while (wait4Merge.length >= 2) {
    const first = wait4Merge.shift()
    let i = 0
    for (; i < wait4Merge.length; i++) {
      const obj = wait4Merge[i]
      const mergedPolygon = mergeTwoPolygons(first, obj)
      if (mergedPolygon.length === 2) { // 合并成功
        if (mergedPolygon === first) {
          merged.push(obj)
        } else if (mergedPolygon === obj) {
          merged.push(first)
        } else {
          merged.push(first, obj)
        }
        wait4Merge.splice(i, 1)
        wait4Merge.push(mergedPolygon)
        break
      }
    }
  }
  // 找出没有合并成功的孤立图形
  const mergeFailedPolygons = verticesHolesArr.filter(arr => !merged.includes(arr) && !wait4Merge.includes(arr))
  return wait4Merge.concat(mergeFailedPolygons)
}

class BoolPolygonsUtil {
  static setPrecision(num = -1) {
    precision = num
    minimum = Math.pow(0.1, num)
  }

  static equalPolygons(polygonA, polygonB) {
    const [aVerts, aIndices] = polygonA
    const [bVerts, bIndices] = polygonB
    if (aVerts.length !== bVerts.length || aIndices.length !== bIndices.length) {
      return false
    }
    for (let i = 0; i < aVerts.length; i++) {
      const a = aVerts[i]
      const b = bVerts[i]
      if (!equals(a, b)) {
        return false
      }
    }
    for (let i = 0; i < aIndices.length; i++) {
      if (aIndices[i] !== bIndices[i]) {
        return false
      }
    }
    return true
  }
  /**
   * @param {{x: number, y: number}} point
   * @param {{x: number, y: number}[]} contour
   * @return {boolean} true point在以contour为轮廓的凸多边形中
   */
  static isInConvex(point, contour) {
    return isInConvex(point, contour)
  }

  static isClockwiseSquence(contour) {
    return isClockwiseSquence(contour)
  }

  static createEdges(contour) {
    const edges = createEdges(contour, 0, 0);
    return edges;
  }

  static isPointInEdges(point, edges) {
    return isPointInEdges0(point, edges) !== POLYGON_OUTSIDE
  }

  /**
   * @param {{x: number, y: number}} point
   * @param {{x: number, y: number}[]} contour 凹或凸的不带孔多边形轮廓
   * @return {boolean} true point在以contour为轮廓的不带孔多边形中
   */
  static isPointInOutline(point, contour) {
    const edges = createEdges(contour, 0, 0)
    return isPointInEdges0(point, edges) !== POLYGON_OUTSIDE
  }

  /**
   * 返回 true 如果顶点 在 带孔多边形中，false 如果顶点在带孔多边形边上 或 外面
   * @param {{x: number, y: number}} point
   * @param {[{x: number, y: number}[], number[] (孔的起始顶点索引) ]} polygon
   */
  static isPointInPolygon(point, polygon) {
    const circles = parseToCircles(polygon, true)
    const edges4Circles = createEdges4Circles(circles, 0)
    const outline = edges4Circles[0]
    const outside = !isPointInEdges(point, outline)
    if (outside) {
      return false
    }
    const inHole = edges4Circles.find((edges, index) => {
      if (index > 0) {
        if (isPointInEdges0(point, edges) !== POLYGON_OUTSIDE) {
          return true
        }
      }
      return false
    })
    return !inHole
  }

  /**
   * 返回 空数组 表示轮廓不是自相交的
   * @param {{x: number, y: number}[]} contour
   * @return {{x: number, y: number}[]} 轮廓自相交后 产生的交点坐标
   */
  static getContourSelfIntersectedPoints(contour) {
    const edges = createEdges(contour, 0, 0)
    const len = edges.length
    const crossPoints = []
    // 依次判断轮廓边 和非邻接边是否有交点
    for (let i = 0; i < len; i++) {
      const edgeA = edges[i]
      for (let j = i + 2; j < len; j++) {
        const edgeB = edges[j]
        if (edgeB.to === edgeA.from) {
          continue
        }
        const crossPoint = segmentsCross(edgeA.from, edgeA.to, edgeB.from, edgeB.to)
        if (crossPoint) { //  && !contour.includes(crossPoint)
          crossPoints.push(crossPoint)
        }
      }
    }
    return crossPoints
  }

  /**
   * @param {{x: number, y: number}[][]} verticesHolesA 最外轮廓是逆时针序列，孔是顺时针序列
   * @param {{x: number, y: number}[][]} verticesHolesB 最外轮廓是逆时针序列，孔是顺时针序列
   * @return {boolean} true： A 包含 B
   */
  static isPolygonAcontainsB(verticesHolesA, verticesHolesB) {
    let contourB = verticesHolesB[0]
    const arr = verticesHolesB[1]
    if (arr.length) {
      contourB = contourB.slice(0, arr[0])
    }
    const circles = parseToCircles(verticesHolesA)
    let edges = []
    circles.forEach((circle, index) => {
      edges = edges.concat(createEdges(circle, 0, index))
    })
    const outPoint = contourB.find(point => isPointInEdges0(point, edges) === POLYGON_OUTSIDE)
    return !outPoint
  }

  /**
   * 返回true表示两个带孔图形 有交集
   * @param {[{x: number, y: number}[], number[] (孔的起始顶点索引) ]} verticesHolesA
   * @param {[{x: number, y: number}[], number[] (孔的起始顶点索引) ]} verticesHolesB
   */
  static isPolygonAintersectsB(verticesHolesA, verticesHolesB) {
    const circlesA = parseToCircles(verticesHolesA)
    const circlesB = parseToCircles(verticesHolesB)
    const edges4CirclesA = createEdges4Circles(circlesA, 0)
    const edges4CirclesB = createEdges4Circles(circlesB, 1)
    const pointAinB = verticesHolesA[0].find(it => isPointInEdges4Circles(it, edges4CirclesB))
    if (pointAinB) {
      return true
    }
    const pointBinA = verticesHolesB[0].find(it => isPointInEdges4Circles(it, edges4CirclesA))
    if (pointBinA) {
      return true
    }
    const segmentsCrossed = splitEdgesOfCircles(edges4CirclesA, edges4CirclesB)
    return segmentsCrossed
  }

  static parseToCircles(verticesHoles) {
    return parseToCircles(verticesHoles, true)
  }

  /**
   * 求多边形 verticesHolesA 减去 verticesHolesB 后的图形
   * @param {{x: number, y: number}[][]} verticesHolesA 最外轮廓是逆时针序列，孔是顺时针序列
   * @param {{x: number, y: number}[][]} verticesHolesB 最外轮廓是逆时针序列，孔是顺时针序列
   * @return {*[]} 返回三维数组，其中每个二维数组的结构和输入参数一致
   */
  static polygonAsubB(verticesHolesA, verticesHolesB) {
    return boolPolygons(verticesHolesA, verticesHolesB, bool_a_sub_b)
  }

  static polygonAintersectB(verticesHolesA, verticesHolesB) {
    return boolPolygons(verticesHolesA, verticesHolesB, bool_intersection)
  }

  static mergePolygons(verticesHolesArr) {
    return mergePolygons(verticesHolesArr)
  }

  /**
   * 合并若干个不带孔的多边形
   * @param {{x: number, y: number}[][]} polygonContours
   * @return {*[]} 每个元素为[[轮廓顶点...], [孔索引...]]
   */
  static mergeNoHolePolygons(polygonContours) {
    if (polygonContours.length < 1) {
      return []
    }
    const verticesHolesArr = []
    polygonContours.forEach(contour => {
      if (isClockwiseSquence(contour)) { // 保证最外轮廓是逆时钟序列
        contour.reverse()
      }
      verticesHolesArr.push([contour, []])
    })
    if (verticesHolesArr.length < 2) {
      return [verticesHolesArr[0]]
    }
    return mergePolygons(verticesHolesArr)
  }

  /**
   * 合并若干个不带孔的多边形，如果合并出图形带孔，丢弃掉孔; polygonContours.length必须大于1
   * @param {{x: number, y: number}[][]} polygonContours
   * @return {{x: number, y: number}[][]}
   */
  static mergeNoHolePolygonsSimply(polygonContours) {
    if (polygonContours.length < 2) {
      return polygonContours
    }
    const mergeResult = this.mergeNoHolePolygons(polygonContours)
    const contourLst = []
    mergeResult.forEach(arr => {
      // 只读取合并后图形的最外轮廓
      let pointLst = arr[0]
      const holeIndices = arr[1]
      if (holeIndices.length) {
        pointLst = pointLst.slice(0, holeIndices[0])
      }
      contourLst.push(pointLst)
    })
    return contourLst
  }

  /**
   * 获取线段和轮廓的若干个交点中 离线段起点最近的一个
   * @param {{x: number, y: number}} segmentStart 线段起点
   * @param {{x: number, y: number}} segmentEnd 线段终点
   * @param {{x: number, y: number}[]} contours 轮廓序列
   * @return {{x: number, y: number}} 交点
   */
  static getClosestLineSegmentCross(segmentStart, segmentEnd, contours) {
    const crossPoints = []
    const len = contours.length
    contours.forEach((point, index) => {
      const next = contours[(index + 1) % len]
      const cross = getLineSegmentCrossPoint(point, next, segmentStart, segmentEnd)
      if (cross) {
        crossPoints.push(cross)
      }
    })
    let minDistance = Infinity
    let target
    crossPoints.forEach(point => {
      const distance = getDistanceSquare(point, segmentStart)
      if (minDistance > distance) {
        minDistance = distance
        target = point
      }
    })
    return target
  }
}

export {BoolPolygonsUtil, bool_a_sub_b, bool_union, bool_intersection, isBetween}
